#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

namespace YX
{
    template<typename W>
    struct BinaryTreeNode 
    {
        struct BinaryTreeNode<W>* _left; 
        struct BinaryTreeNode<W>* _right;
        W _w;

        BinaryTreeNode(const W& w)
            :_left(nullptr)
            ,_right(nullptr)
            ,_w(w)
        {

        }
    };

    template<class W,bool B=true>
    class BinaryTree 
    {
        typedef struct BinaryTreeNode<W> Node;
        private:
            Node* _root;
            unordered_map<W,int> _index;

            // 前序构建
            Node* prev_BinaryTree(const vector<W>& prevorder,const vector<W>& inorder,int p_left,int p_right,int i_left,int i_right)
            {
                if(p_left>p_right)
                {
                    return nullptr;
                }
                
                int root_index=_index[prevorder[p_left]];

                Node* newNode=new Node(prevorder[p_left]);

                newNode->_left=prev_BinaryTree(prevorder,inorder,p_left+1,p_left+(root_index-i_left),i_left,root_index-1);
                newNode->_right=prev_BinaryTree(prevorder,inorder,p_right-(i_right-root_index)+1,p_right,root_index+1,i_right);

                return newNode;
            }

            // 后序构建
            Node* post_BinaryTree(const vector<W>& postorder,const vector<W>& inorder,int p_left,int p_right,int i_left,int i_right)
            {
                if(p_left>p_right)
                {
                    return nullptr;
                }
                
                int root_index=_index[postorder[p_right]];

                Node* newNode=new Node(postorder[p_right]);

                newNode->_left=post_BinaryTree(postorder,inorder,p_left,p_left+(root_index-i_left)-1,i_left,root_index-1);
                newNode->_right=post_BinaryTree(postorder,inorder,p_right-(i_right-root_index),p_right-1,root_index+1,i_right);

                return newNode;
            }

            void _PrevOrder(Node* root)
            {
                if(root==nullptr)
                {
                    return;
                }
                
                cout<<root->_w<<" ";
                _PrevOrder(root->_left);
                _PrevOrder(root->_right);
            }

            void _InOrder(Node* root)
            {
                if(root==nullptr)
                {
                    return;
                }
                
                _InOrder(root->_left);
                cout<<root->_w<<" ";
                _InOrder(root->_right);
            }
        public:
            BinaryTree(const vector<W>& order,const vector<W>& inorder)
                :_root(nullptr)
            {
                
                int n=inorder.size();

                _index.clear();

                for(int i=0;i<n;i++)
                {
                    _index[inorder[i]]=i;
                }

                if(B==true)
                {
                   _root=prev_BinaryTree(order,inorder,0,n-1,0,n-1);
                }
                else if(B==false) 
                {
                    _root=post_BinaryTree(order,inorder,0,n-1,0,n-1);
                }

            }

            void PrevOrder()
            {
                _PrevOrder(_root);
                cout<<endl;
            }

            void InOrder()
            {
                _InOrder(_root);
                cout<<endl;
            }

    };

    void TestBinaryTree()
    {
//        vector<int> p={3,9,20,15,7};
//        vector<int> i={9,3,15,20,7};
//        
//        BinaryTree<int> tree(p,i);
//
//        tree.PrevOrder();
//
        vector<int> p={9,15,7,20,3};
        vector<int> i={9,3,15,20,7};
        
        BinaryTree<int,false> tree(p,i);

        tree.InOrder();
        tree.PrevOrder();
    }


};
